When a computer application provides data of a page to a device for printing and/or display, an intermediate description of the page is often given to device driver software in a page description language (PDL). The intermediate description of the page includes descriptions of the graphic objects to be rendered. This contrasts with some arrangements where raster image data is generated directly by the application and transmitted for printing or display. Examples of page description languages include LIPS™ (Canon Inc. of Japan) and PCL™ (Hewlett-Packard Inc. of USA).
Equivalently, the application may provide a set of descriptions of graphic objects via function calls to a graphics device interface layer (GDI), such as the Microsoft Windows™ GDI (Microsoft Corp. of USA). The printer driver for the associated target printer is the software that receives the graphic object descriptions from the GDI layer. For each graphic object, the printer driver is responsible for generating a description of the graphic object in the page description language that is understood by the rendering system of the target printer.
The rendering system of the printer contains a PDL interpreter that parses the graphic object descriptions and builds a display list (DL) of graphic object data. The rendering system also contains a raster image processor (RIP) that processes the display list and renders the data to an output page image of pixel values The pixel values typically comprise for example cyan (C), magenta (M), yellow (Y) and black (K) colour channels. Once in this format, the printer prints the page.
A graphic object can be a fill region, which (potentially) contributes colour to the output image, or a clip region. Hereinafter, “graphic object” will be taken to mean “fill region”.
Each graphic object may further be affected, modified or “clipped” by a clip region. The clip region limits the graphic objects it clips to the boundaries of the clip region. The clip region may describe a rectangular shape, called a clip rectangle, or describe a more complex shape, called a clip path.
There are two types of clip regions. Inclusive clip regions, called “clip-ins”, are where graphic objects are only drawn inside the boundaries of the clip region. Exclusive clip regions, called “clip-outs”, are where graphic objects are only drawn outside the boundaries of the clip region.
The clip region (or simply “clip”) may be applied to a single graphic object or a group of graphic objects. A clip region that clips a group of graphic objects is deemed to be “active” over the group of graphic objects. Furthermore, a graphic object or group of graphic objects may be clipped by two or more clip regions. A graphic object's “clipping status” is the list of clips that clip that graphic object.
Most RIPs utilize a large volume of memory, known in the art as a frame store or a page buffer, to hold a pixel-based image data representation of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled with colour values and written into the frame store. For two-dimensional computer graphics, objects that appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel by pixel basis. This is commonly known in the art as “Painter's algorithm”; also as “object-sequential rendering”. Objects are considered in priority order, from the rearmost object to the foremost object, and typically, each object is rasterised in scanline order and pixels are written to the frame store in sequential runs along each scanline. These sequential runs are termed “pixel runs”. Some RIPS allow objects to be composited with other objects in some way. For example, a logical or arithmetic operation can be specified and performed between one or more semi-transparent graphic objects and the already rendered pixels in the frame buffer. In these cases, the rendering principle remains the same: objects are rasterised in scanline order, and the result of the specified operation is calculated and written to the frame store in sequential runs along each scanline.
There are a number of problems with the Painter's algorithm rendering method. One of the problems is that many pixels which are written to the framestore by rasterising an object are subsequently over-written when rasterising later objects. There is a clear disadvantage in using resources to write pixel data into a framestore that will, at a later stage, be over-written.
Another problem is that when an object requires compositing, pixels beneath the object are typically read from the framestore and combined in some way with the pixels of the object. If the pixels in the framestore are stored in a lower bit-depth than the object requiring compositing, then most compositing operations generate an incorrect result. This is the case when the graphics object is, for example, an 8 bit per channel RGBA bitmap and the framestore holds one bit per channel half-toned pixel data. This can occur because pixel values are often stored in a framestore at the bit depth required for printing. Although it is possible to store pixels at the full bit depth of the original object fills, e.g. 8 or more bits per channel, an 8 bit per channel RGBA framestore at 600 dpi resolution requires over 100 MB of memory for an A4 page. Also, once the page is rendered to the 8 bit per channel framestore, it must still be converted to the lower bit depth for printing, which is inefficient.
Other RIPs may utilise a pixel-sequential rendering approach to remove the need for a framestore. In these systems, each pixel is generated in raster order along scanlines. All objects to be drawn are retained in a display list in an edge-based format. On each scanline, the edges of objects that intersect the current scanline, known as active edges, are held in increasing order of their points of intersection with the scanline. These points of intersection, or edge crossings, are considered in turn, and activate or deactivate objects in the display list. Between each pair of edges considered, the colour data for each pixel which lies between the first edge and the second edge is generated based on which objects are active for that run of pixels. In preparation for the next scanline, the coordinate of intersection of each edge is updated in accordance with the properties of each edge, and the edges are sorted into increasing order of point of intersection with that scanline. Any newly active edges are also merged into the ordered list of active edges. Graphics systems which use pixel-sequential rendering have significant advantages over object-sequential renderers in that there is no frame store or line store and no unnecessary over-painting. Objects requiring compositing are processed on a per-pixel basis using each object's original colour data. Each pixel is converted to the output bit depth after any compositing, so the correct result is obtained regardless of the output bit depth.
Pixel-sequential rendering suffers when there are large numbers of edges that must be tracked and maintained in sorted order for each scanline. As each edge is updated for a new scanline, the edge is re-inserted into the active edge list, usually by an insertion sort. For complex pages, which may consist of hundreds of thousands of edges, the time required to maintain the sorted list of active edges for each scanline becomes a large portion of the total time to render a complex page.
In a situation where a framestore of less than full bit depth is available, a “hybrid” rendering approach may be employed. The display list is partitioned into one or more groups of objects requiring compositing, and one or more groups of objects not requiring compositing. Pixel-sequential rendering is used for the groups of objects requiring compositing, and object-sequential rendering is used for the remaining object groups. Another alternative to overcome memory constraints is to store only a portion, or band, of the full bit depth output image in memory at any one time. Conventional “banded renderers” render the display list to the band buffer or “band store”, one band at a time, starting at the top and working consecutively down the page. While this requires no modification to a pixel-sequential renderer, it is highly inefficient to employ a conventional object-sequential renderer in this fashion, as the entire display list must be traversed once for each band. Additionally, it is inefficient to perform object-sequential compositing to a bandstore, particularly when the objects are specified at lower bit depth than the bandstore. A hybrid renderer employing a conventional object-sequential renderer to render objects not requiring compositing would remove this latter inefficiency, but would still inherit at least part of the former inefficiency.
In a Painter's algorithm RIP, there are a number of approaches to dealing with clipping regions. In one approach, the clip region is divided into multiple clip rectangles, where each rectangle is a single scanline high. As the graphic object is rasterized, each determined pixel-run is intersected with any clipping rectangles present on that scanline, and only those pixels within the clipping rectangles are output. In another approach, both the edges of the graphic object and the edges that define the clipping region(s) are scan converted using active edge list (AEL) techniques. A global clip-counter is maintained and typically set to zero at the start of each scanline. Edges are processed on each scanline in increasing x-order. When an edge is processed that activates a clipping region, the clip-counter is incremented. Similarly, when an edge is processed that deactivates a clipping region, the clip-counter is decremented. Pixels are only output between edge pairs inside a graphic object when the clip-counter is equal to the number of active clip regions clipping this graphic object.
Regardless of which approach is used, in a Painter's algorithm RIP each graphic object, from rearmost to foremost, must be clipped by all active clip regions before that graphic object is output to the frame store. In the case where a clip region clips all graphic objects on the page, then that clip region is typically processed as many times as there are graphic objects on the page.
In a pixel-sequential RIP, clipping is typically achieved through the use of a clip list, which is a list of pointers to all graphic objects that are clipped by the clip region. Each clip region has a clip list. Each graphic object also has a clip-count property, which is initialised to the number of clip regions that clip this graphic object.
Each time a clip region is activated or deactivated on a scanline, the associated clip list is traversed, and each graphic object's clip-count is decremented on activation, or incremented on deactivation. A graphic object then only contributes pixels to a pixel-run between two edge pairs when the graphic object's clip-count is zero. So, in the simplest case of a rectangular clip region, the clip-counts of all graphic objects clipped by the clip region are modified twice per scanline over the number of scanlines that the clip region is active. They are clipped once when the clip becomes active on a scanline, and again when the clip becomes inactive on a scanline.
Although a pixel-sequential RIP has the advantage that a clip region is processed only once, it can be seen that the performance of such a RIP can degrade substantially when the number of entries in the clip list is large, and when the clip region itself has a large number of edge crossings per scanline.